/*
 * @lc app=leetcode id=84 lang=cpp
 *
 * [84] Largest Rectangle in Histogram
 */
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();

        int maxArea = 0;
        for (int i = 0; i < len; i++) {
            if (i+1 < len && heights[i] < heights[i+1]) {
                continue;
            }

            int minHeight = heights[i];
            int area = 0;
            for (int j = i; j >= 0; j--) {
                minHeight = std::min(minHeight, heights[j]);
                area = minHeight * (i-j+1);
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        return maxArea;
    }
};

